package com.feng.leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author feng
 * @decrition
 * @date 2022/11/323:27
 */
public class L60 {
    public static String getPermutation(int n, int k) {
        List<String> list = new ArrayList<>();
        List<String> result = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            getNums(list, i, result);
            list = result;
            result = new ArrayList<>();
        }
        Collections.sort(list);
        return list.get(k - 1);
    }

    private static void getNums(List<String> list, int i, List<String> result) {
        if (list.isEmpty()) {
            result.add(i + "");
            return;
        }
        for (int j = 0; j < list.size(); j++) {
            String s = list.get(j);
            for (int k = 0; k <= s.length(); k++) {
                StringBuilder sb = new StringBuilder(s);
                StringBuilder insert = sb.insert(k, i);
                result.add(insert.toString());
            }
        }
    }
}
